package com.bee.剑指offer;

import java.util.ArrayList;
import java.util.List;

/**
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
 *
 * @version 1.0.0
 * @Author yong.Mr
 * @data 20121-04-30
 */
public class 二叉搜索树与双向链表 {

    public TreeNode Convert(TreeNode root) {
        List<TreeNode> temp = new ArrayList<TreeNode>();
        TreeNode first = null;
        inRound(root, temp);
        if (temp.size() == 1) {
            return root;
        }
        for (int i = 0; i < temp.size(); i++) {
            // 最后一个结点
            if (i == temp.size() - 1) {
                temp.get(i).left = temp.get(i - 1);
            } else if (i == 0) {
                first = temp.get(i);
                temp.get(i).right = temp.get(i + 1);
            } else {
                temp.get(i).right = temp.get(i + 1);
                temp.get(i).left = temp.get(i - 1);
            }
        }
        return first;
    }

    public void inRound(TreeNode root, List<TreeNode> temp) {
        if (root == null) {
            return;
        }
        inRound(root.left, temp);
        int val = root.val;
        temp.add(root);
        inRound(root.right, temp);
    }

    public static void main(String[] args) {

    }
}
